/**
 * 70. Climbing Stairs
 * https://leetcode.com/problems/climbing-stairs/
 */
package lc70;

public class Main {
  public static void main(String[] args) {
    int n = 10;
    Solution s = new Solution();
    System.out.println(s.climbStairs(n));
  }
}

class Solution {
  public int climbStairs(int n) {
    if (n < 3) return n;
    int a = 1, b = 2, c = 0;
    for (int i = 2; i < n; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }
}

class Solution2 {
  public int climbStairs(int n) {
    if (n < 3) return n;
    int[] arr = new int[n];
    arr[0] = 1;
    arr[1] = 2;
    for (int i = 2; i < n; i++) {
      arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n - 1];
  }
}

class Solution3 { // recursive
  public int climbStairs(int n) {
    if (n < 3) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
  }
}
